|
In number theory, a probable prime is a number that passes a primality test. A strong probable prime is a number that passes a ''strong'' version of a primality test. A strong pseudoprime is a composite number that passes a strong version of a primality test. All primes pass these tests, but a small fraction of composites also pass, making them "false primes". Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all coprime bases (the Carmichael numbers), there are no composites that are strong pseudoprimes to all bases. ==Formal definition== Formally, an odd composite number ''n'' = ''d'' · 2''s'' + 1 with ''d'' also odd is called a strong (Fermat) pseudoprime to a relatively prime base ''a'' when one of the following conditions holds: : or : (If a number ''n'' satisfies one of the above conditions and we don't yet know whether it is prime, it is more precise to refer to it as a strong probable prime to base ''a''. But if we know that ''n'' is not prime, then one may use the term strong pseudoprime.) The definition of a strong pseudoprime depends on the base used; different bases have different strong pseudoprimes. The definition is trivially met if so these trivial bases are often excluded. Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.〔Guy, ''Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes.'' §A12 in ''Unsolved Problems in Number Theory'', 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「strong pseudoprime」の詳細全文を読む スポンサード リンク
|